package lc;
import java.util.*;
import org.junit.*;
public class Ms17_24 {
    class Solution {
        int m, n;
        public int[] getMaxMatrix(int[][] matrix) {
            int max = Integer.MIN_VALUE;
            int[] res = new int[4];
            m = matrix.length;
            n = matrix[0].length;
            int[] nums = new int[n];
            //前缀和的数组
            int[][] tmp = new int[m + 1][n];
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < n; j++) {
                    tmp[i][j] = tmp[i - 1][j] + matrix[i - 1][j];
                }
            }
            //遍历两行（行上界与行下界)
            for (int i = 0; i < m; i++) {
                for (int j = i + 1; j <= m; j++) {
    
                    //上下行界限中的列之和
                    for (int k = 0; k < n; k++) {
                        nums[k] = tmp[j][k] - tmp[i][k];
                    }
    
                    //计算最大子序和
                    int[] t = maxSubArr(nums);
                    if (t[2] > max) {
                        res[0] = i;
                        res[1] = t[0];
                        res[2] = j - 1;
                        res[3] = t[1];
                        max = t[2];
                    }
                }
            }
            return res;
        }
    
        public int[] maxSubArr(int[] nums) {
            int max = nums[0], tmp = nums[0];
            int[] res = new int[3];
            res[0] = res[1] = 0;
            for (int i = 1; i < n; i++) {
                int t = Math.max(nums[i], nums[i] + tmp);
                if (t > max) {
                    if (t == nums[i] + tmp) {
                        res[1] = i;
                    } else {
                        res[0] = i;
                        res[1] = i;
                    }
                    max = t;
                }
                tmp = t;
            }
            res[2] = max;
            return res;
        }
    
        /**
            1. 一维的最大子序和：f[i] = Math.max(nums[i], f[i - 1] + nums[i]);
    
            2. 一维记录最大子序的始末位置：
            在nums[i] > f[i - 1] + nums[i]时， begin记录这个下标
    
            3. 二维的最大子矩阵：
            利用前缀和，将每一列的几行元素求和，作为i处的nums[i]
            难点：如何遍历所有行的选取方案？
         */
    
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = {new int[]{-1, 0}, new int[]{0, -1}};
        System.out.println(Arrays.toString(s.getMaxMatrix(nums)));
    }
}
